The general methods of error control in data communication links are forward error correction (FEC), overlaying an automatic repeat request (ARQ) scheme, or using a combination of both, which is referred to as hybrid-ARQ (HARQ). In both ARQ and HARQ the presence of errors is detected by using an error detecting code.
A common technique to change data rates in communication systems is by the use of puncturing. In this technique some number of parity symbols, which are formed by a mother code, are not transmitted. Before decoding at the receiver a proper number of known symbols (zeros) are inserted at the locations of the punctured symbols, and then a decoder for the unpunctured mother code is used. Note that puncturing is a suboptimal technique resulting in a performance loss. In the case of convolutional codes this loss can be made negligible by an optimization of puncturing masks.
Rate compatible codes were first proposed for convolutional codes by J. Hagenauer et. al, “The performance of rate-compatible punctured convolutional codes for future digital mobile radio” in Proc. IEEE Vehicular Technology Conference 1988, pp. 22-29, Jun. 1988. In that case the punctured convolutional codes were organized in such a way that all coded symbols of higher coding rate are used for decoding lower rate codes. This concept was later extended to rate compatible turbo codes (RCTC) accepted for the Third Generation Partnership Project (3GPP) standardization.
Recently introduced concatenated zigzag codes (see L. Ping, X. Huang and N. Phamdo, “Zigzag Codes and Concatenated Zigzag Codes”, IEEE Trans. Information Theory, vol. 47, pp. 800-807, February 2001) are shown to provide comparable or improved (at high coding rates) performance to turbo codes. At the same time the decoding complexity of concatenated zigzag codes is about 10 times less, and it may be reduced even further as suggested by the present inventor in commonly assigned US Patent Publications US 2004/0123215 A1, Jun. 24, 2004 “Low Decoding Complexity Concatenated Codes for High Rate Coded Transmission” and US 2004/0123216 A1, “Low Complexity Decoding Schemes for Single-Parity-Check (SPC) Based Concatenated Codes”, Jun. 24, 2004, incorporated by reference herein, as well as in N. Nefedov, “Multi-Dimensional Zigzag Codes for High Data Rate Transmission”, Int. Symp. on Turbo Codes and its Applications (ISTCA2003), Brest, France, September 2003.
On the other hand, since parallel concatenation of zigzag (PCZZ) codes inherit some structural properties of block codes, the construction is made more complicated for compatible coding rates required for HARQ (although similar problem can be observed for LDPC codes, which may be presented as a generalization of zigzag codes). One technique to provide different data rates for link adaptation is the use of data reshaping, as is addressed in US 2004/0123215 A1 and in commonly assigned U.S. Patent application Ser. No. 10/971,681, “Flexible Rate and Punctured Zigzag Codes”, by Prabodh Varshney et al. Also, multi-dimensional zigzag codes for HARQ schemes are proposed in US 2004/0123215 A1.